package Offer;

/**
 * @author lakersUp
 * @Classname   nthUglyNumber
 * @Description    丑数,动态规划三指针
 * @Date 2022/2/27 10:16
 * @Version 1.0
 */
public class Offer49nthUglyNumber {
    public int nthUglyNumber(int n) {
        int p2,p3,p5;
        p2=p3=p5=0;
        int[] dp=new int[n];
        dp[0]=1;
        int nums2,nums3,nums5;
        for(int i=1;i<n;i++){
            nums2=2*dp[p2];
            nums3=3*dp[p3];
            nums5=5*dp[p5];
            dp[i]=Math.min(nums2,Math.min(nums5,nums3));
            if(dp[i]==nums2){
                p2++;
            }
            if(dp[i]==nums3){
                p3++;
            }
            if(dp[i]==nums5){
                p5++;
            }
        }
        return dp[n-1];
    }
}
